Introduction: Compliance with the recommendation that all tuberculosis (TB) patients be tested for human immunodeficiency virus (HIV) has not yet been achieved in Canada or globally. Methods: The experience of “opt-out” HIV testing of TB patients in the Province of Alberta, Canada is described over a 10-year period, 2003–2012. Testing rates are reported before and after the introduction of the “opt-out” approach. Risk factors for HIV seropositivity are described and demographic, clinical and laboratory characteristics of TB patients who were newly diagnosed versus previously diagnosed with HIV are compared. Genotypic clusters, defined as groups of two or more cases whose isolates of Mycobacterium tuberculosis had identical DNA fingerprints over the 10-year period or within 2 years of one another, were analyzed for their ability to predict HIV co-infection. Results: HIV testing rates were 26% before and 90% after the introduction of “opt-out” testing. During the “opt-out” testing years those <15 or >64 years of age at diagnosis were less likely to have been tested. In those tested the prevalence of HIV was 5.6%. In the age group 15–64 years, risk factors for HIV were: age (35–64 years), Canadian-born Aboriginal or foreign-born sub-Saharan African origin, and combined respiratory and non-respiratory disease. Compared to TB patients previously known to be HIV positive, TB patients newly discovered to be HIV positive had more advanced HIV disease (lower CD4 counts; higher viral loads) at diagnosis. Large cluster size was associated with Aboriginal ancestry. Cluster size predicted HIV co-infection in Aboriginal peoples when clusters included all cases reported over 10 years but not when clusters included cases reported within 2 years of one another. Conclusion: “Opt-out” HIV testing of TB patients is effective and well received. Universal HIV testing of TB patients (>80% of patients tested) has immediate (patients) and longer-term (TB/HIV program planning) benefits.